#include <cstdio>
#include <algorithm>

using namespace std;

char str[100005];

template <typename T> inline void read(T &r){
  char c;bool f=0;
  for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
  for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
  if(f) r=-r;
}

int main(){
  register int n,q;

  freopen("lncp.in","r",stdin);
  freopen("lncp.out","w",stdout);

  read(n);read(q);
  scanf("%s",str);

  while(q--){
    int i,j,k;
    read(i);read(j);
    i--;j--;
    if(i>j) swap(i,j);
    for(k=0;str[j+k]&&str[i+k]!=str[j+k];k++);
    printf("%d\n",k);
  }

  return 0;
}

